package main

import (
	"fmt"
	"math"
)

// 如何获取最好的矩阵链相乘方法

func main() {
	arr := []int{1, 5, 2, 4, 6}
	fmt.Println("最少的乘法次数为：", bestMatrixChainOrder(arr))
}

func bestMatrixChainOrder(arr []int) int {
	n := len(arr)
	cost := make([][]int, n)
	for i := range cost {
		cost[i] = make([]int, n)
	}

	// cLen 指的是执行乘法运算的矩阵的数量
	for cLen := 2; cLen < n; cLen++ {
		// i 指的是起始矩阵的标号
		for i := 1; i+cLen-1 < n; i++ {
			// j 指的是终止矩阵的标号
			j := i + cLen - 1
			cost[i][j] = math.MaxInt64
			for k := i; k <= j-1; k++ {
				q := cost[i][k] + cost[k+1][j] + arr[i-1]*arr[k]*arr[j]
				if q < cost[i][j] {
					cost[i][j] = q
				}
			}
		}
	}

	return cost[1][n-1]
}
